During program instruction execution at the microprocessor level, an indirect branch instruction may cause execution to jump to a non-sequential instruction somewhere else in the program, rather than the next sequential instruction. Predicting to which instruction the execution will branch is an important optimization. There are two types of predictable indirect branches, “simple” indirect branches and “polymorphic” indirect branches. “Simple” indirect branches are branches that keep jumping to the same target instruction. “Polymorphic” indirect branches are branches that jump to different target instructions in a specific pattern that is usually predictable.
A global indirect branch predictor stores a history of the correct target for all conditional branches. Simple indirect branches do not need a global branch history for accurate prediction, but polymorphic indirect branches do. While building a large monolithic indirect predictor that uses global branch history may solve the problem, it is not feasible to build such an array from an area and timing perspective of a processor. Multiple clock cycles would be needed to lookup such a large predictor and that may have a negative impact on the performance of the application.
Further, in many cases, using global branch history can harm simple branches in a two-fold way. First, it may provide a bad prediction of simple branches while the global branch history is being populated. Second, the same branch may now be stored in multiple entries of the indirect predictor array, creating a capacity problem even though it would have been perfectly acceptable to allocate the simple branch in only one entry because it always jumps to the same target.
What is needed is a way to predict both simple and polymorphic indirect branches accurately without negatively impacting the timing or the performance of the processor.